/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：二维区域和检索 - 矩阵不可变</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
 * </pre>
 * <p>创建日期：2019年11月28日下午3:32:55</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code304RangeSumQuery2dImmutable</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code304RangeSumQuery2dImmutable
{
	int[][]	dp	= null;

	public static void main(String[] args)
	{
		/**
		 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。


		上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

		示例:

		给定 matrix = [
		[3, 0, 1, 4, 2],
		[5, 6, 3, 2, 1],
		[1, 2, 0, 1, 5],
		[4, 1, 0, 1, 7],
		[1, 0, 3, 0, 5]
		]

		sumRegion(2, 1, 4, 3) -> 8
		sumRegion(1, 1, 2, 2) -> 11
		sumRegion(1, 2, 2, 4) -> 12
		说明:

		你可以假设矩阵不可变。
		会多次调用 sumRegion 方法。
		你可以假设 row1 ≤ row2 且 col1 ≤ col2。
		 */
		int[][] matrix = new int[][] { { 3, 0, 1, 4, 2 }, { 5, 6, 3, 2, 1 }, { 1, 2, 0, 1, 5 }, { 4, 1, 0, 1, 7 }, { 1, 0, 3, 0, 5 } };
		Code304RangeSumQuery2dImmutable immutable = new Code304RangeSumQuery2dImmutable(matrix);
		int sumRegion = immutable.sumRegion(1, 2, 2, 4);
		System.out.println(sumRegion);
	}

	/**
	 * 这个题的解题思路非常精彩，建议看leetcode的官方题解
	 * 判空暂时不处理，这个真是麻烦
	 * @param matrix
	 */
	/**
	 * dp的存储矩阵：
	 *  0	0	0	0	0	0	
		0	3	3	4	8	10	
		0	8	14	18	24	27	
		0	9	17	21	28	36	
		0	13	22	26	34	49	
		0	14	23	30	38	58
	 * @param matrix
	 */
	public Code304RangeSumQuery2dImmutable(int[][] matrix)
	{
		dp = new int[matrix.length + 1][matrix[0].length + 1];
		for (int i = 0; i < matrix.length; i++)
		{
			for (int j = 0; j < matrix[i].length; j++)
			{
				dp[i + 1][j + 1] = matrix[i][j] + dp[i][j + 1] + dp[i + 1][j] - dp[i][j];
			}
		}
		for (int i = 0; i < dp.length; i++)
		{
			for (int j = 0; j < dp[i].length; j++)
			{
				System.out.print(dp[i][j] + "\t");
			}
			System.out.println();
		}
	}

	/**
	 * Your NumMatrix object will be instantiated and called as such:
	 * NumMatrix obj = new NumMatrix(matrix);
	 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
	 */
	public int sumRegion(int row1, int col1, int row2, int col2)
	{
		return dp[row2 + 1][col2 + 1] + dp[row1][col1] - dp[row1][col2 + 1] - dp[row2 + 1][col1];
	}
}
